package gti310.tp3.solver;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Stack;

import gti310.tp3.parser.*;

/**
 * La classe ConcereteSolver implémente l'interface Solver avec sa méthode Solve.
 * Son rôle dans le programme est de fournir une solution de chemin optimale 
 * pour un graphe donné. 
 * 
 * @author Fredy A. Bonilla et Emile Robinson
 * @date 2014-11-08
 */
public class ConcreteSolver implements Solver<E,T>{

	//Constantes
	private final static int SOURCE = 0;
	private final static int DESTINATION = 1;
	private final static int POIDS = 2;

	//Les différentes listes utilisées
	private List<Sommet> chemin;
	List<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();

	//Variables
	private GraphList graph;
	private int depart;

	/**
	 * Conscteur de la classe pas défaut. 
	 */
	public ConcreteSolver(){};

	/**
	 * Complete the required task based on the input E and return an output
	 * object T. The method should return null if the task cannot be completed
	 * properly.
	 * 
	 * @param input The object required to complete the task.
	 * @return A user defined object, or null if something went wrong.
	 */
	public T solve(E input) {

		T result = null;
		depart = input.getSommetDepart();

		//Construction du graphe
		graphMaker(input);	

		//Parcour des chemins possibles
		findPaths();

		//Enregirstrement des résultats obtenus
		result = new T();
		result.savePath(paths);

		return result;
	}

	/**
	 * Méthode privée servant à la construction d'un graphe. Elle reçoit en 
	 * paramètre l'objet E contenant les informations pour sa construction.
	 * 
	 * @param e
	 */
	private void graphMaker(E e){

		Sommet s1 = null;
		Sommet s2 = null;
		int index=0;

		graph = new GraphList();

		//Créations des sommets
		for(int i=0; i<e.getSources().size(); i++){

			//Creation du sommet et d'une liste de voisins
			s1 = new Sommet(e.getSources().get(i));
			s1.creerListeVoisins();

			//Valeur infini par défaut
			s1.setMinDistance(e.getValeurInfinie());

			//ajout du sommet dans la graphe
			graph.ajouter(s1);
		}

		//Creation des voisins de chaque sommets
		for(int i=0; i<e.getSources().size(); i++){
			for(int j=0; j<e.getTailleListe(); j++){

				//Si le sommet existe déja dans le graphe
				if(graph.getSommet(i).getId() == e.getInnerListe(j).get(SOURCE)){

					index = e.indexOf(e.getInnerListe(j).get(DESTINATION));
					s2 = graph.getSommet(index);

					//Creation de la connexion avec le voisin et le poids
					graph.getSommet(i).connectTo(s2, e.getInnerListe(j).get(POIDS));

				}

			}
		}

		System.out.println("Graphe construit");
		System.out.println("Nombre de sommets: "+graph.getGraph().size());
	}

	/**
	 * Initialise les listes de visites et démarre la recherche des chemins  
	 * La recherche part du premier sommet dans le graph et parcourt chacun des 
	 * voisins de ce sommet
	 * 
	 */
	public void findPaths() {	    	    

		List<Integer> visite = new ArrayList<Integer>();
		visite.add(depart);
		Integer sommetActuel = depart;

		//Parcour de tous les voisins
		for (Connector c : graph.getGraph().get(depart).getVoisins())  {	        
			sommetActuel = c.getSource().getId(); 
			findAllPaths(graph, visite, paths, sommetActuel);

		}
	}

	/**
	 * Parcourt le graph a partir du sommetActuel et 
	 * place son chemin dans la liste parcouru et 
	 * dans la liste des chemins
	 * 
	 * @param graph, visite, paths, sommetActuel
	 */
	private void findAllPaths(GraphList graph, List<Integer> visite,
			List<ArrayList<Integer>> paths, Integer somActuel) {

		if(visite.size() < graph.getTaille()){

			if (somActuel.equals(depart)) { 
				paths.add(new ArrayList<Integer>(visite));

				//sommet Actuel -1, étant donné que la méthode getSommet attend un index
				LinkedList<Connector> voisins = graph.getSommet(somActuel-1).getVoisins(); 	        

				//Parcour de tous les voisins
				for (Connector c : voisins) {	            
					List<Integer> temp = new ArrayList<Integer>();
					temp.addAll(visite);
					temp.add(c.getSource().getId()); 
					
					//Appel de la méthode récursivement
					findAllPaths(graph, temp, paths, c.getDestination().getId());
				}

			}

			else {
				//sommet Actuel -1, étant donné que la méthode getSommet attend un index
				LinkedList<Connector> voisins = graph.getSommet(somActuel-1).getVoisins(); 	
				
				//Parcour de tous les voisins
				for (Connector c : voisins) {            
					if (visite.contains(c)) {
						continue;
					} 
					List<Integer> temp = new ArrayList<Integer>();
					temp.addAll(visite);	            
					temp.add(c.getSource().getId()); 
					
					//Appel de la méthode récursivement
					findAllPaths(graph, temp, paths, c.getDestination().getId());
				}
			}

		}

	} 

}
